package two;
import java.util.*;





public class A033 {


    public ListNode sortList(ListNode head) {
        //1.遍历一遍，将val和节点放入数据结构中
        //2.使用数据结构的排序方法按照val进行排序
        //3.再次组装链表

        List<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while(cur!=null) {
            ListNode next = cur.next;
            cur.next=null;
            list.add(cur);
            cur=next;
        }
        list.sort((node1,node2)->Integer.compare(node1.val, node2.val));
        ListNode dummy = new ListNode();
        cur=dummy;
        for(ListNode t:list) {
            cur.next = t;
            cur=cur.next;
        }
        return dummy.next;
    }
}
